/**
 * @file quicksort.cpp
 * @author 水若可长 (SherlockZhang@aliyun.com)
 * @brief 快排,递归,
 * i从左向右j从右向左,如果i指向的值大于key,i就暂停,
 * 等到j指向的值小于key的时候交换i和j指向的值,
 * 最后当j碰到i时交换j指向的值和key的值,交换后j所指向的值左侧都小于他,右侧都大于他
 * @version 0.1
 * @date 2021-03-2
 *
 * @copyright Copyright (c) 2023
 *
 **/
#include <iostream>
#include "../printarr.h"
using namespace std;

void QuickSort(int arr[], int left, int right)
{
    if (arr == NULL)
        return;
    if (left >= right)
        return;
    int i = left;
    int j = right;
    int key = arr[left];
    while (1)
    {
        while (arr[i] <= key)
        {
            i++;
            if (i == right)
                break;
        }
        while (arr[j] >= key)
        {
            j--;
            if (j == left)
                break;
        }
        if (i >= j)
        {
            break; // 此处break是跳出while(1)这个循环
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    arr[left] = arr[j];
    arr[j] = key;
    QuickSort(arr, left, j - 1);
    QuickSort(arr, j + 1, right);
}

int main()
{
    int sort_array[10] = {6, 1, 2, 5, 9, 3, 4, 7, 10, 8};
    PrintArr(sort_array, "before quicksort sort_array is: ");
    QuickSort(sort_array, 0, 9);
    PrintArr(sort_array, "after quicksort sort_array is: ");
    return 0;
}
